package c066;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * ClassName: c02
 * Package: c066
 * Description: 983. 最低票价 https://leetcode.cn/problems/minimum-cost-for-tickets/description/
 *
 *
 *
 *
 *
 在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。

 火车票有 三种不同的销售方式 ：

 一张 为期一天 的通行证售价为 costs[0] 美元；
 一张 为期七天 的通行证售价为 costs[1] 美元；
 一张 为期三十天 的通行证售价为 costs[2] 美元。

 通行证允许数天无限制的旅行。 例如，如果我们在第 2 天获得一张 为期 7 天 的通行证，那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。

 返回 你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费 。

 1 <= days.length <= 365
 1 <= days[i] <= 365
 days 按顺序严格递增
 costs.length == 3
 1 <= costs[i] <= 1000

 * @Author BCXJ
 * @Create 2025/11/30 23:11
 * @Version 1.0
 * @Since 1.0
 */
public class c02 {

    public static void main(String[] args) {
        int[] arr1 = {1,4,6,7,8,20};
        int[] arr2 = {2, 7, 15};
        System.out.println(mincostTickets(arr1, arr2));
    }

    static int[] durations = {1, 7, 30};
    // 暴力解法
    public static int mincostTickets(int[] days, int[] costs) {
        return f1(days, costs, 0);
    }

    // 从 i - length - 1的最小花费
    private static int f1(int[] days, int[] costs, int i) {
        if(i == days.length) {
            return 0;
        }
        int cost = Integer.MAX_VALUE;
        for (int j = i, k = 0; k < 3; k ++) {
            while(j < days.length && days[i] + durations[k] > days[j]) {
                j ++;
            }
            cost = Math.min(cost, costs[k] + f1(days, costs, j));
        }

        return cost;
    }

    // 傻缓存法
    static int[] ans = new int[365];
    public static int mincostTickets2(int[] days, int[] costs) {
        Arrays.fill(ans, -1);
        return f2(days, costs, 0);
    }
    // 从 i - length - 1的最小花费
    private static int f2(int[] days, int[] costs, int i) {
        if(i == days.length) {
            return 0;
        }
        if(ans[i] != -1) {
            return ans[i];
        }
        int cost = Integer.MAX_VALUE;
        for (int j = i, k = 0; k < 3; k ++) {
            while(j < days.length && days[i] + durations[k] > days[j]) {
                j ++;
            }
            cost = Math.min(cost, costs[k] + f2(days, costs, j));
        }
        ans[i] = cost;
        return cost;
    }

    // dp 方式（标准动态规划)


}
